Optimisation est le processus mathématique de recherche de la "meilleure" solution — soit en minimisant, soit en maximisant une fonction objectif — dans une région admissible définie, soumise à des contraintes spécifiques.
Méthodes classiques vs. méthodes intelligentes
- Méthode de Newton-Raphson : Approche itérative de recherche de racines utilisant les dérivées d'ordre deux (matrice hessienne).
- Descente de gradient : Méthode du premier ordre qui se déplace vers le minimum local en suivant le gradient négatif.
- Algorithmes évolutionnaires (AE) : Méthodes de recherche stochastiques basées sur une population, inspirées de la sélection naturelle biologique.
Concepts essentiels
Il est essentiel de distinguer entre le vecteur décision (les variables que nous modifions) et la fonction objectif (le critère de réussite).
Pièges liés au codage
Attention aux gradient qui s'efface dans les méthodes basées sur le calcul différentiel et aux falaises de Hamming dans les algorithmes évolutionnaires codés en binaire. Une simple augmentation décimale (par exemple, de 7 à 8) peut nécessiter le changement de tous les bits (de 0111 à 1000), ce qui crée une « falaise » empêchant l'efficacité de la recherche. Utilisez le codage de Gray pour atténuer ce problème.
Implémentation Python : descente de gradient
Question 1
Pourquoi un problème d'optimisation convexe est-il considéré comme « plus facile » qu'un problème non convexe ?
Question 2
Dans le cadre des algorithmes évolutionnaires, que représente le « phénotype » ?
Étude de cas : Maximisation de l'aire d'un triangle
Lisez le scénario ci-dessous et répondez aux questions de formulation.
Considérez le problème de maximiser l'aire d'un triangle rectangle dont la longueur de l'hypoténuse $c$ est fixe.
Q
1. Identifiez les variables de décision et la fonction objectif.
Réponse :
Variables : Les longueurs des deux côtés adjacents, $a$ et $b$.
Fonction objectif : Maximiser $Area = \frac{1}{2} \cdot a \cdot b$.
Variables : Les longueurs des deux côtés adjacents, $a$ et $b$.
Fonction objectif : Maximiser $Area = \frac{1}{2} \cdot a \cdot b$.
Q
2. Énoncez la contrainte fondée sur les propriétés géométriques.
Réponse :
D'après le théorème de Pythagore, la contrainte est : $a^2 + b^2 = c^2$.
D'après le théorème de Pythagore, la contrainte est : $a^2 + b^2 = c^2$.
Q
3. Si l'on utilise la méthode de Newton-Raphson, quelle matrice doit être calculée pour tenir compte des dérivées partielles d'ordre deux ?
Réponse :
La matrice hessienne ($H$), qui contient toutes les dérivées partielles d'ordre deux de la fonction objectif.
La matrice hessienne ($H$), qui contient toutes les dérivées partielles d'ordre deux de la fonction objectif.